package 力扣题库;

import 剑指offer.ListNode;

public class p142环形链表II {
    public ListNode detectCycle(ListNode head) {
        //找环的入口点
        //使用快慢指针
        //经过画图推导可以发现：从快慢指针的相遇点到环的入口点的距离 == 从起始位置到环的入口点的距离

        ListNode fast=head;
        ListNode slow=head;

        //先找相遇点  b
        while (fast!=null && fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow) {
                break;
            }
        }
        //如果没有环，则返回null
        if (fast==null || fast.next==null) {
            return null;
        }

        slow=head;
        while (slow!=fast) {
            slow=slow.next;
            fast=fast.next;
        }
        return fast;

    }
}
